package 动态规划.另类的;

import org.junit.Test;

import java.util.Arrays;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/1/3 18:10
 */
public class leetcode300最长上升子序列 {

     /*
      这个 题的 最优解 是 O(N * lgN)
      有点难想
      之后 有空 可以 把 灵神的 基础算法 精讲 给看一下:
      https://www.bilibili.com/video/BV1ub411Q7sB/?vd_source=179da737184de5a8f84e4f6c2ee5c350
      */


    /*
    这三道题 放在一块 一起 思考下:
     最大 子数组 和 lc 53
     lc: 674. 最长连续递增序列
     */



   /*
    这个题 有点类似于  ** 子数组的最大和问题 **
    这种类型题的 一个 典型的特点 ： 暴力递归 没办法 一次 求出 最优解！
    int nums [] = {10,9,2,5,3,7,101,18};
     递归 函数  f(index) 表示的 含义 为 以 index 开头的 最长 递增子序列
     但是 问题就 出在 这里 ，f（index） 不一定 是 最后的结果
     即 f（index） 不一定 > f(index + 1)
     从 nums 数组中就看出这个问题了
     10 开头的 最长曾序列  2
     但是 以 2 开头的 最长增序列 4
     意思 就是 f(0) 不一定是 最后的 结果!

     1.一种方法就是 可以 通过 记忆化搜索 先把 dp表填好, 然后遍历 找出最优解


    */
    public static void main(String[] args) {
        int nums [] = {10,9,2,5,3,7,101,18};
//        int nums [] = {18};
        int recursion = recursion(0, nums);
        System.out.println(recursion);
//        System.out.println(a);
        System.out.println(solution(nums));
//        System.out.println(Arrays.toString());
        System.out.println(dpNew(nums));
    }

    /*
        这是 正序 遍历的 dp 表（每次 i 遍历 填表的 情况）
        [2, 0, 0, 0, 0, 0, 1, 1, 0]
        [2, 2, 0, 0, 0, 0, 1, 1, 0]
        [2, 2, 4, 3, 3, 2, 1, 1, 0]
        [2, 2, 4, 3, 3, 2, 1, 1, 0]
        [2, 2, 4, 3, 3, 2, 1, 1, 0]
        [2, 2, 4, 3, 3, 2, 1, 1, 0]
        [2, 2, 4, 3, 3, 2, 1, 1, 0]
        [2, 2, 4, 3, 3, 2, 1, 1, 0]
     */
    public static int solution(int nums[]){
        int len = nums.length;
        int  [] dp = new int[len + 1];
        int ans = 0;
        for(int i = len - 1;i >= 0;i--){
            ans = Math.max(ans,recursion(i,nums,dp));
            System.out.println(Arrays.toString(dp));
        }
        return ans;
    }

    public static int recursion(int index,int [] nums,int dp[]){
        // nums[index] 本身 长度 1
        if(dp[index] != 0){
            return dp[index];
        }
        int ans = 1;
        for(int j = index + 1;j < nums.length;j++){
            if(nums[index] < nums[j]){
                ans = Math.max(ans,recursion(j,nums,dp) + 1);
            }
        }
        return dp[index] = ans;
    }



    /*
 这个递归 只能求出， 以  index  开头的 最长递增子序列的长度

 f(index) 的含义: 就是 以index 开头的最长子序列的长度!
 */
    public static int recursion(int index,int [] nums){
        // nums[index] 本身 长度 1
        int ans = 1;
        for(int j = index + 1;j < nums.length;j++){
            if(nums[index] < nums[j]){
                ans = Math.max(ans,recursion(j,nums) + 1);
            }
        }
        return ans;
    }



    /*
      将上面的 暴力 改成 dp 之后
      直接 把 O(N ^ 2) 的解法 给改出来了

      ******对比 solution 和  dp  这两个方法 *****
      有一种妙不可言的感觉
     */
    public int dp(int []nums){
        int len = nums.length;
        int [] dp = new int[len];
        int ans = 1;
        for(int index = len - 1;index >=0 ; index--){
            dp[index] = 1;
            for(int j = index + 1;j < len;j++){
                if(nums[index] < nums[j]){
                    dp[index] = Math.max(dp[index],dp[j] + 1);
                }
            }
            ans = Math.max(dp[index],ans);
        }
        return ans;
    }





    /*
      2023/3/9
      这里面有一个 很坑的 一个点:
      比如 这个序列 : 2,5,3,4,101,18
       2 , 5 ,18 (or 101) 序列 并不 是最优解
       2 , 3 , 4 , 18(or 101) 才是最优解
       需要 枚举 所有的  在 2 后面的 比 2 大的 数值, 才能确定最优解!
     */
    public static int dpNew(int nums[]){
        int dp[] = new int[nums.length + 1] , ans = 0;
        dp[nums.length - 1] = 1;
        for(int i = nums.length - 2;i >= 0;i--){
            int j;
            for( j = i + 1;j < nums.length; j++){
                // 严格 递增 的序列
                if(nums[i] < nums[j]){
                    dp[i] = Math.max(dp[i],dp[j] + 1);
                }
            }
            ans = Math.max(ans,dp[i]);
        }
        return ans;
    }

    @Test
    public void test(){
        int nums [] = {10,9,2,5,3,7,101,18};
        System.out.println(dp(nums));
        System.out.println(dpNew(nums));

    }




}
